跳到主要内容

2379.得到 K 个黑块的最少涂色次数

· 阅读需 4 分钟

1、题干​

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。

给你一个整数 k ，表示想要 连续 黑色块的数目。

每一次操作中，你可以选择一个白色块将它 涂成 黑色块。

请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。

 

示例 1：

输入：blocks = "WBBWWBBWBW", k = 7
输出：3
解释：
一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。
得到 blocks = "BBBBBBBWBW" 。
可以证明无法用少于 3 次操作得到 7 个连续的黑块。
所以我们返回 3 。

示例 2：

输入：blocks = "WBWBBBW", k = 2
输出：0
解释：
不需要任何操作，因为已经有 2 个连续的黑块。
所以我们返回 0 。

 

提示：

  • n == blocks.length
  • 1 <= n <= 100
  • blocks[i] 要么是 'W' ，要么是 'B' 。
  • 1 <= k <= n

2、思路1​

双层遍历，每次取 k 个色块，对白色块计数，取最少白色块数

3、代码​

function minimumRecolors(blocks: string, k: number): number {
    let ans = k;
    for (let i = 0; i < blocks.length; i++) {
        for (let j = i, w = 0; j - i < k && j < blocks.length; j++) {
            if (blocks[j] === 'W') w++;
            if (j - i + 1 === k) ans = Math.min(w, ans);
        }
    }
    return ans;
};

4、复杂度​

  • 时间复杂度：O(nk)O(nk)
  • 空间复杂度：O(1)O(1)

5、执行结果​

image.png

6、思路2​

滑动窗口求解，窗口固定长度为 k，对窗口内白色块计数，取最少白色块数

7、代码​

function minimumRecolors(blocks: string, k: number): number {
    let w = 0;
    for (let i = 0; i < k; i++) {
        if (blocks[i] === 'W') w++;
    }

    let ans = w;
    for (let i = k; i < blocks.length; i++) {
        if (blocks[i - k] === 'W') w--;
        if (blocks[i] === 'W') w++;
        ans = Math.min(w, ans);
    }
    
    return ans;
};

也可以这样

function minimumRecolors(blocks: string, k: number): number {
    let ans = k, w = 0;
    for (let i = 0, j = i; i < blocks.length; i++) {
        for (; j < i + k && j < blocks.length; j++) {
            if (blocks[j] === 'W') w++;
        }
        if (j - i === k) ans = Math.min(w, ans);
        if (blocks[i] === 'W') w--;
    }
    return ans;
};

8、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(1)O(1)

9、执行结果​

image.png